package cn.edu.bjut.my.thinkinjava._20200427_slideWindow;

import java.util.HashMap;

/**
 * 用于测试滑动窗口代码
 *
 * 题目：给定字符串S，一个字符串T，请在S中找出包含T所有字符的最小子串:
 * 例：  s = "ADOBECODEBANC"   t = "ABC";
 * 输出：BANC
 *
 * <p>
 * 1：暴力解法：双层for循环
 * 2：滑动窗口方法：
 * 使用左右两个指针
 * 2.1右指针右移
 * 2.1.1如果当前字符为需要字符，使用window记录窗口内某字符含有的次数
 * 2.1.2使用valid记录window中多少种字符满足需求
 * 2.2当valid==targe字符种类时：
 * 2.2.1left++
 * 2.2.2记录比较截取的start、length
 * 2.2.3如果删除的字符为需要的字符，更新window和valid
 */
public class SlideWindow {

    public String slideWindowTest(String s, String t) {
        //记录目标字符串字符种类和需要字符数量
        HashMap<Character, Integer> need = new HashMap();
        //记录窗口内含有目标字符串的种类和每种字符串的数量
        HashMap<Character, Integer> window = new HashMap();

        for (char c : t.toCharArray()) {
            need.put(c, need.get(c) == null ? 1 : need.get(c) + 1);
        }

        int left = 0, right = 0;
        //记录need与window含有目标字符串的种类数
        int valid = 0;
        // 记录最小覆盖子串的起始索引及长度
        int start = 0, len = Integer.MAX_VALUE;
        while (right < s.length()) {
            // c 是将移入窗口的字符
            char c = s.charAt(right);
            // 右移窗口
            right++;
            // 进行窗口内数据的一系列更新
            if (need.get(c) != null) {
                window.put(c, window.get(c) == null ? 1 : window.get(c) + 1);
                if (window.get(c) == need.get(c))
                    valid++;
            }

            // 判断左侧窗口是否要收缩
            while (valid == need.size()) {
                // 在这里更新最小覆盖子串
                if (right - left < len) {
                    start = left;
                    len = right - left;
                }
                // d 是将移出窗口的字符
                char d = s.charAt(left);
                // 左移窗口
                left++;
                // 进行窗口内数据的一系列更新
                if (need.get(d) != null) {
                    if (window.get(d) == need.get(d))
                        valid--;
                    window.put(d, window.get(d) - 1);
                }
            }
        }
        // 返回最小覆盖子串
        return len == Integer.MAX_VALUE ?
                "" : s.substring(start, start + len);
    }

    public static void main(String[] args) {
        String s = "ADOBECODEBANC";
        String t = "ABCB";
        System.out.println(new SlideWindow().slideWindowTest(s, t));

    }
}
